package basicSort.quickSort;

//三路快排 分三段 ,减少递归次数

public class ThreeQuickSort {

    public static int[] threeQuicksort(int[] arr){
        if( arr == null || arr.length < 2 ){
            return arr;
        }

        threePsort( arr , 0 , arr.length - 1 );

        return arr;
    }

    public static void threePsort( int[] arr , int l , int r ){
        if( l < r ){
            int[] p = threePartion( arr , l , r);
            threePsort( arr, l , p[0]);
            threePsort( arr, p[1] , r);
        }
    }

    public static int[] threePartion( int[] arr , int l , int r ){
        int index = l - 1;
        int random = (int) Math.random() * (r-l) + l;
        swap( arr , random , r);
        int flag = arr[r];
        int rindex = r;
        while ( l < rindex ){
            if( arr[l] < flag ){
                swap( arr , ++index , l++);
            }else if( arr[l] > flag ){
                swap( arr ,  l , --rindex );
            }else {
                l++;
            }
        }
        swap( arr , r , rindex);

        return new int[]{index,rindex+1};
    }

    public static void swap(int[] arr , int i ,int j ){
        int temp = arr[i] ;
        arr[i] = arr[j] ;
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int count = 10000;

        //int[] arr = new int[count];

        for ( int i = 0 ; i < count ; i++){
            //arr[i] =(int) (Math.random() * 100);
        }
        int[] arr = new int[]{2,0,2,1,1,0};
        threeQuicksort(arr);

        for( int i = 0 ; i < arr.length ; i++){
            System.out.print(arr[i]+" ");
        }
    }

}
